Multiprocessor scheduling

In computer science, multiprocessor scheduling is an NP-complete optimization problem. The problem statement is: "Given a set J of jobs where job j_i has length l_i and a number of processors m_i, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.

Algorithms

A simple, often-used algorithm is the LPT algorithm (Longest Processing Time) which sorts the jobs by its processing time and then assigns them to the machine with the earliest end time so far. This algorithm achieves an upper bound of 4/3 - 1/(3m) OPT.^[1]

See also

• Job shop scheduling, a similar problem for scheduling jobs on machines. Some variants of multiprocessor scheduling and job shop scheduling are equivalent problems.

References

1. ^ Graham, R. L. (1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics 17 (2): 416–429. 

• A compendium of NP optimization problems. Editors: Pierluigi Crescenzi, and Viggo Kann [1]